package pers.qianyu.month_202012.date_20201218;

import pers.qianyu.util.model.*;

/**
 * 382. 链表随机节点
 * https://leetcode-cn.com/problems/linked-list-random-node/
 *
 * @author mizzle rain
 * @date 2020年12月18日17:17:53
 */
public class RandomListNode {
    // 蓄水池算法
    private ListNode head;

    public RandomListNode(ListNode head) {
        this.head = head;
    }

    public int getRandom() {
        int res = 0;
        int i = 0;
        ListNode p = head;
        while (p != null) {
            i++;
            double r = Math.random();
            if (r < 1.0 / i) {
                res = p.val;
            }
            p = p.next;
        }
        return res;
    }
}